package com.lgc.algorithm.other;

import java.util.Arrays;

public class Main2 {
    public static void main(String[] args) {
        int[] nums = {10, 2, 8, 1, 2, 3, 5, 2, 3};
//        int[] nums = {10, 2, 8, 1, 2, 3};
        int[] indexArr = getIndexArray(nums);


        for (int i = 0; i < indexArr.length; i++) {
            System.out.println(indexArr[i]);
        }

        System.out.println(Arrays.toString(indexArr));
    }

    public static int[] getIndexArray(int[] nums) {
        int[] result = new int[nums.length];

        TreeNode root = null;
        for (int i = 0; i < nums.length; i++) {
            root = addNode(root, new TreeNode(i, nums[i]));
        }

        read(root, result);

        return result;
    }

    public static TreeNode addNode(TreeNode root, TreeNode newNode) {
        if (root == null) {
            root = newNode;

            return root;
        }

        if (root.val < newNode.val) {
            newNode.smallCount = root.smallCount + 1 + root.sameCount;
            root.right = addNode(root.right, newNode);
        } else {
            if (root.val > newNode.val) {
                root.smallCount += 1;
            } else {
                newNode.smallCount = root.smallCount;

                root.sameCount += 1;
                newNode.sameCount = root.sameCount;
            }

            // root的所有右侧节点的count+1
            root.right = addCount(root.right, 1);

            root.left = addNode(root.left, newNode);
        }

        return root;
    }

    public static TreeNode addCount(TreeNode root, int value) {
        if (root == null) {
            return null;
        }

        root.smallCount += 1;

        root.left = addCount(root.left, 1);
        root.right = addCount(root.right, 1);

        return root;
    }

    public static void read(TreeNode node, int[] result) {
        if (node == null) {
            return;
        }

        result[node.index] = node.smallCount;
        read(node.left, result);
        read(node.right, result);
    }
}

class TreeNode {
    public int index;
    public int val;
    public int smallCount;//比当前节点值小的数的个数
    public int sameCount;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int index, int val) {
        this.index = index;
        this.val = val;
    }
}
